package com.code.orderArray;

/**
 * 有序数组的增删改查，使用到了二分法
 */
public class OrderArray {

    private long[] a;
    /*数组中元素的个数*/
    private int nElems;

    public OrderArray(int max) {
        a = new long[max];  //构造器中创建数组
        nElems = 0;
    }

    public int size() {
        return nElems;
    }

    /**
     * 二分法查找
     *
     * @param searchKey 查找的元素
     * @return 元素下标
     */
    public int find(long searchKey) {
        int lowerBound = 0; //最小下标
        int upperBound = nElems - 1; //最大下标
        int curIn;  //当前下标

        while (true) {
            curIn = (lowerBound + upperBound) / 2;
            if (a[curIn] == searchKey) {
                return curIn;   //找到
            } else if (lowerBound > upperBound) {
                return nElems;  //未找到
            } else {
                //循环遍历
                if (a[curIn] < searchKey) {
                    lowerBound = curIn + 1;
                } else {
                    upperBound = curIn - 1;
                }
            }
        }
    }

    public void insert(long value) {
        int j;
        //查找value插入的位置
        for (j = 0; j < nElems; j++) {
            if (a[j] > value) {
                /*这里纠正我认识中的误区，break后不会再执行j++，也就是说j的坐标就是比value大的值的坐标*/
                break;
            }
        }

        /*把更大的数的下标增加一位*/
        for (int k = nElems; k > j; k--) {
            a[k] = a[k - 1];
        }
        a[j] = value;
        nElems++;
    }

    public boolean delete(long value) {
        int j = find(value);
        if (j == nElems) {
            return false;   //未找到
        } else {
            for (int k = j; k < nElems; k++) {    //将更大的数前移一位
                a[k] = a[k + 1];
            }
            nElems--;
            return true;
        }
    }


    public void display() {
        for (int j = 0; j < nElems; j++) {
            System.out.print(a[j] + " ");
        }
        System.out.println("");
    }
}
